package A_review.review1_15;

public class MergeSort {

    public  int[]  mergeSort(int[] nums){

        if (nums.length==0){
            return  null;
        }
        int[] temp=new int[nums.length];
        sort(nums,0, nums.length-1,temp );

        return  nums;
    }


    public   void  sort(int[] nums,int lo,int hi,int[] temp){

        if (lo>=hi){
            return;
        }
        int mid=(lo+hi)/2;
        sort(nums, lo,mid,temp);
        sort(nums, mid+1, hi,temp);
        merge(nums,lo,mid,hi,temp);

    }


    public  void  merge(int[] nums,int lo,int mid,int hi,int[] temp){
        int i=0;
        int j=lo;
        int k=mid+1;
        while (j<=mid&&k<=hi){
            if (nums[j]<=nums[k]){
                temp[i++]=nums[j++];
            }else {
                temp[i++]=nums[k++];
            }
        }
        while (j<=mid){
            temp[i++]=nums[j++];
        }
        while (k<=hi){
            temp[i++]=nums[k++];
        }

        for (int l = 0; l < i; l++) {
            nums[lo+l]=temp[l];
        }


    }

    public static void main(String[] args) {
        MergeSort mergeSort = new MergeSort();
        int[] cur={2,4,12,45,1,3};
       cur= mergeSort.mergeSort(cur);
        for (int a:cur) {
            System.out.println(a);
        }
    }


}
